package binary_tree.Heap.leetcode;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @Description: 最后一块石头的重量
 * @Author Stark
 * @Date 2022/3/8 20:38
 **/
public class Num1046_WeightOfLastStone {
    public int lastStoneWeight(int[] stones) {
        //使用大堆进行存储
        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for(int tmp : stones){
            queue.offer(tmp);
        }
        //当堆中大于一个的时候继续循环
        while(queue.size() > 1){
            //每次取出两个值,并且y总是>=x
            int y = queue.poll();
            int x = queue.poll();
            //y > x,将剩余部分入堆,继续循环
            if(y > x){
                y = y - x;
                queue.offer(y);
            }
        }
        if(queue.isEmpty()){
            return 0;
        }else{
            return queue.poll();
        }
    }
}
